小编vor*_*192的帖子

到目前为止,我已经了解了如何std::deque在引擎盖下实现,并发现它类似于指向n字节数组的指针数组,其中数据实际存储在其中.所以现在我有几个与deques相关的问题.

描述我目前对其结构的了解的图片:

问题是:

1. 当push_front正在执行操作并且数据块0中没有可用空间时,在堆上分配新的数据块,并且将指向这个新分配的内存的指针插入到'Map'数组中,就像在普通数组中一样 - 在O(number_of_blocks)中)时间,是吗？

2. 如何对这种野兽进行排序？无法想象更好的事情然后将所有数据复制到数组中,对其进行排序,然后将其放回原处.但这种方法需要O(n)辅助内存......但是!std::sort提供类似的接口,用于排序std::vector和std::deque.如何实现不同数据结构的不同算法？使用模板专业化？如果是这样,为什么std::list不能使用std::sort？或者,也许,std::sort不关心这个容器的内部结构和只使用迭代器和方法,是在这两个相似的std::vector和std::deque(如operator[],size()等)？这个想法听起来很合理,并且回答"为什么不能std::sort排序std::list？" 变得明显.

3. 如何选择数据块的大小？你会说"它依赖于实现",但请详细说明解决方案背后的不同实现和动机.

需要澄清这里.谢谢.

维基百科声称可以在O(n)时间内计算失败函数表.

让我们看看它的"规范"实现(在C++中):

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

为什么它在O(n)时间内工作,即使存在内部while循环？我对算法的分析并不是很强,所以有人可以解释一下吗？

正如您从标题中所知,我正在尝试使用PriorityQueue进行多处理.更确切地说,我想制作共享的PriorityQueue,编写了一些代码并且它没有像我预期的那样运行.

看看代码:

import time
from multiprocessing import Process, Lock
from Queue import PriorityQueue


def worker(queue):
    lock = Lock()
    with lock:
        for i in range(100):
            queue.put(i)

    print "worker", queue.qsize()


pr_queue = PriorityQueue()
worker_process = Process(target = worker, args = (pr_queue,))
worker_process.start()

time.sleep(5)    # nope, race condition, you shall not pass (probably)
print "main", pr_queue.qsize()

得到以下输出:

worker 100
main 0

发生了什么以及如何以正确的方式做我想做的事情？谢谢.

我只想使用最简单的算法生成一些迷宫,但我的所有迷宫看起来都像以下一样:

这是一段Java代码(whatVisit函数工作正常,不要看它):

private void dfs(Point start, boolean[][] visited) {
    Point nextCell = whatVisit(start, visited);
    if(nextCell == null)        // if there's nothing to visit
        return;

    // mark current cell as visited
    visited[start.y][start.x] = true;
    // destroy the wall between current cell and the new one
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true;

    // start a new search from found cell
    dfs(nextCell, visited);
}

private Point whatVisit(Point p, boolean[][] visited) {
    Vector<Point>cells = new Vector<Point>();   // to store acessible cells

    // lookaround …

我正在写一个代表图形的类,所以我写了下面的标题

class Graph {
public:
  Graph(); 
  Graph(int N);

  void addVertex();
  void addEdge(VertexNum v1, VertexNum v2, Weight w);


  std::pair<PathLength, Path> shortestPath
    (const VerticesGroup& V1, const VerticesGroup& V2);


private:
  typedef int                           VertexNum;
  typedef int                           Weight;
  typedef std::pair<VertexNum, Weight>  Edge;
  typedef std::vector<Edge>             Path;
  typedef size_t                        PathLength;
  typedef std::vector<VertexNum>        VerticesGroup;


  std::vector<std::list<Edge> > adjList;

  bool incorrectVertexNumber(VertexNum v);
};

我对上面的代码有一些疑问:

1. 我应该声明一堆typedef是public还是private？
2. 这是一种常规做法,当一个type将一个类型解析为不同的同义词时(比如typedef int VertexNum; typedef int Weight;)？

我在以下构造中遇到恼人的语法错误:

isPrime n = if numOfDivisors n == 0 then True else False            
    where numOfDivisors n = length $ [x | x <- [2..ceiling (sqrt n)], n `mod` x == 0]

我怎么解决它？我是Haskell的新手,所以我不知道出了什么问题[2..ceiling (sqrt n)].

谢谢(抱歉我脑子不好).

可以在关键字用在C++中的东西被使用,除非关键字的命名空间？如果不是 - 为什么我们不能简单地写" 命名空间...... "？如果是 - 您可以在"非命名空间"的上下文中给出一些它的用法示例吗？

谢谢.

如何声明带数字和数字列表的函数,如果列表中没有这样的数字则返回NONE,否则返回list选项(Haskell中的'Maybe')没有这个数字？如果有多于一个这样的数字,则函数必须首先擦除它们中的第一个.

all_except_one : 'a * 'a list -> 'a list option

我不知道该怎么做:\我问任何语言的代码,只是关于函数式算法的一些提示(最初我必须在SML中解决这个问题).此外,我不能在我的任务中使用高阶函数.

到目前为止,我发现,我完全不了解std :: vector的本质.

让我解释:

矢量是可以增长的,对吧？这意味着,在内部它必须以某种方式动态分配/重新分配内存.像这样的东西:

class vector {
private:
    int *data;
};

好的.但是这样的定义意味着如果我们通过引用或值将std :: vector传递给另一个函数 - 这两种类型的参数传递之间没有区别,并且两个函数都能够修改数据(除非vector是作为const传递).

但!我尝试了以下内容,但我的想法失败了:

void try_to_modify(vector<int> v) {
    v[2] = 53;
}

int main() {
    vector<int> v(3);
    v[2] = 142;
    try_to_modify(v);
    cout << v[2] << '\n';    // output is: 142

    return 0;
}

那真相在哪儿？什么std :: vector真的是？

谢谢.