Вопрос:

Как построить новый вектор / набор указателей из другого вектора / набора объектов?

c++ c++11 pointers vector set

127 просмотра

2 ответа

6834 Репутация автора

Фон

Я хотел манипулировать копией вектора, однако выполнение операции копирования вектора для каждого его элемента обычно является дорогостоящей операцией.

Есть понятие, называемое мелкой копией, которое я где-то читал - это поведение конструктора копирования по умолчанию. Однако я не уверен, почему это не работает, или, по крайней мере, я попытался сделать копию векторного объекта, и результат выглядит как глубокая копия.

struct Vertex{
    int label;
    Vertex(int label):label(label){ }
};

int main(){
    vector<Vertex> vertices { Vertex(0), Vertex(1) };

    // I Couldn't force this to be vector<Vertex*>      
    vector<Vertex> myvertices(vertices); 

    myvertices[1].label = 123;

    std::cout << vertices[1].label << endl; 
    // OUTPUT: 1 (meaning object is deeply copied)

    return 0;
}

Наивное решение: для копирования указателя.

int main(){
    vector<Vertex> vertices { Vertex(0), Vertex(1) };

    vector<Vertex*> myvertices;
    for (auto it = vertices.begin(); it != vertices.end(); ++it){
        myvertices.push_back(&*it);
    }

    myvertices[1].label = 123;

    std::cout << vertices[1].label << endl;
    // OUTPUT: 123 (meaning object is not copied, just the pointer)

    return 0;
}

улучшение

Есть ли другой лучший подход или std::vectorAPI для создания нового вектора, содержащего только указатель каждого из элементов в исходном векторе?

Автор: Yeo Источник Размещён: 22.08.2016 08:51

Ответы (2)


2 плюса

33194 Репутация автора

Решение

Одним способом вы могли бы преобразовать вектор элементов в вектор указателей, которые указывают на элементы исходного вектора, что лучше с точки зрения эффективности по сравнению с вашим примером, из-за того, что он предварительно выделяет буфер вектора указателей, И ИМХО более элегантным является использование std::transformследующим образом:

std::vector<Vertex*> myvertices(vertices.size());
std::transform(vertices.begin(), vertices.end(), myvertices.begin(), [](Vertex &v) { return &v; });

Live Demo

Или, если вы не хотите использовать лямбду для унарного оператора:

std::vector<Vertex*> myvertices(vertices.size());
std::transform(vertices.begin(), vertices.end(), myvertices.begin(), std::addressof<Vertex>);

Live Demo

Внимание: если вы изменяете исходный вектор, то вы лишаете законной силы указатели в векторе указателей.

Автор: 101010 Размещён: 22.08.2016 09:16

0 плюса

6834 Репутация автора

Спасибо за @kfsone за то, что обратили внимание на главную проблему, что очень редко люди хотели отслеживать указатель от другого вектора объекта, не используя основную идею, стоящую за ним. Он предоставил альтернативный подход, который решает подобную проблему с помощью битовой маскировки. Это может быть не очевидно для меня, пока он не упомянул это.

Когда мы пытаемся сохранить только указатели другого вектора, мы, скорее всего, хотели бы отследить, хранить (отслеживать) другой объект. Что позже будет выполнено на самом указателе, не касаясь исходных данных. В моем случае я решаю проблему минимального покрытия вершин с помощью брутфорс-подхода. При этом мне нужно будет сгенерировать всю перестановку вершин (например, 20 вершин сгенерируют перестановку 2 ** 20 = 1 миллион ++), затем я обрежу все нерелевантные перестановки, медленно перебирая каждую из вершин в покрытии вершин и удаляя ребра, которые покрыты вершины. При этом моей первой интуицией является копирование всех указателей для обеспечения эффективности, а затем я могу просто удалить указатель один за другим.

Однако, другой способ решения этой проблемы - не использовать вектор / набор вообще, а просто отслеживать каждый из этих указателей как битовый шаблон. Я не буду вдаваться в детали, но не стесняйтесь учиться у других .

Разница в производительности очень значительна, так что в побитовом режиме вы можете без особых проблем достичь O (1) постоянного времени, в то время как при использовании конкретного контейнера вам, как правило, приходится повторять каждый из элементов, которые связывают ваш алгоритм с O (n). Что еще хуже, если вы решаете трудную проблему NP, вам нужно поддерживать постоянный коэффициент как можно ниже, и от O (1) до O (N) - огромная разница в таком сценарии.

Автор: Yeo Размещён: 23.08.2016 02:11
Вопросы из категории :
32x32