извиняюсь за большой вопрос

возникли сложности с подходящим алгоритмом

есть структура

enum T {A, B, C, D, E};
struct S{
    T type;
    int count;
    S (T t, int c) : type (t), count (c){;}

    bool operator == (const S& s){
        return type == s.type;
    }
    void operator += (const S& s){
        count += s.count;
    }
    void operator << (const S& s){
        type = s.type;
        count += s.count;
    }

};

const S operator+ (const S& lhs, const S& rhs){
    return S (lhs.type, lhs.count + rhs.count);
}

1. Есть вектор объектов

    std::vector<S> v1(3);
    std::vector<S> v2(3);

нужно каждый элемент 1 списка объединить с каждым элементом второго
я смог это сделать только так

    std::transform (v1.begin(), v1.end(),
            v2.begin(), v1.begin(),
            std::plus<S>());

но для каждой пары создается новый объект и перезаписывается на место в 1 векторе
получается слишком много вызовов конструкторов и деструкторов

2. есть список

    std::list<S> list;
    list.push_back(S (A, 50));
    list.push_back(S (B, 200));
    list.push_back(S (C, 300));
    list.push_back(S (A, 50));

нужно объединить равные объекты
тоесть должно получиться в списке
S (A, 100);
S (B, 200);
S (C, 300);

3. нужно сделать тоже если они в разных списках

    std::list<S> list1;
    list1.push_back(S (A, 50));
    list1.push_back(S (B, 200));
    list1.push_back(S (C, 300));

    std::list<S> list2;
    list2.push_back(S (A, 50));
    list2.push_back(S (E, 500));

тоесть А из второго списка должен объединиться с А из первого списка и удалиться из 2
в результате должно получиться

list1;
S (A, 100);
S (B, 200);
S (C, 300);

list2;
S (E, 500);

Здравствуйте, cthutq00, Вы писали:

C>

C>enum T {A, B, C, D, E};
C>struct S{
C>    T type;
C>    int count;
C>    S (T t, int c) : type (t), count (c){;}

C>    bool operator == (const S& s){
C>        return type == s.type;
C>    }
C>    void operator += (const S& s){
C>        count += s.count;
C>    }
C>    void operator << (const S& s){
C>        type = s.type;
C>        count += s.count;
C>    }

C>};

C>const S operator+ (const S& lhs, const S& rhs){
C>    return S (lhs.type, lhs.count + rhs.count);
C>}

C>

Не очень, если честно, мне хотелось бы быть на месте пользователей этого класса. Я бы заменил некоторые операторы (особенно operator<<) на функции-члены с осмысленными именами. Во всяком случае обычно ожидают, что сигнатура и эффект у перегруженных операторов будет такой же, как у встроенных типов. Ну да ладно, не мне судить, не зная ситуации.

C>1. Есть вектор объектов

C>

C>    std::vector<S> v1(3);
C>    std::vector<S> v2(3);

C>

C>нужно каждый элемент 1 списка объединить с каждым элементом второго
C>я смог это сделать только так

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

C>

C>    std::transform (v1.begin(), v1.end(),
C>            v2.begin(), v1.begin(),
C>            std::plus<S>());

C>

Ну вместо transform лучше использовать merge, мне кажется, в данном случае.

C>но для каждой пары создается новый объект и перезаписывается на место в 1 векторе
C>получается слишком много вызовов конструкторов и деструкторов

Хм, ну тогда

    for (unsigned i = 0; i < v1.size(); ++i)
        v1[i] += v2[i];

Никаких конструкторов и деструкторов и читается хорошо. По-хорошему индексную переменную надо заменить на итераторы, но из-за компактности написал так.

C>2. есть список

C>

C>    std::list<S> list;
C>    list.push_back(S (A, 50));
C>    list.push_back(S (B, 200));
C>    list.push_back(S (C, 300));
C>    list.push_back(S (A, 50));

C>

C>нужно объединить равные объекты
C>тоесть должно получиться в списке
C>S (A, 100);
C>S (B, 200);
C>S (C, 300);

Предлагаю завести map<T, int>, проитерироваться по списку, сбрасывая все в map, а потом построить новый list по полученному map'у. Если же enum никогда изменяться не будет (но вообще, лучше не делать таких предположений обычно), можно вместо map'a воспользоваться vector<int>.

C>3. нужно сделать тоже если они в разных списках

C>

C>    std::list<S> list1;
C>    list1.push_back(S (A, 50));
C>    list1.push_back(S (B, 200));
C>    list1.push_back(S (C, 300));

C>    std::list<S> list2;
C>    list2.push_back(S (A, 50));
C>    list2.push_back(S (E, 500));

C>

C>тоесть А из второго списка должен объединиться с А из первого списка и удалиться из 2
C>в результате должно получиться

C>list1;
C>S (A, 100);
C>S (B, 200);
C>S (C, 300);

C>list2;
C>S (E, 500);

Тут на самом деле не совсем понятно, что надо сделать. Предлагаю тоже самое, сначала забрасываем в map первый список, потом выборочно (проверяем, если такой элемент в map'е) забрасываем в map второй вместе с удалением забрасываемых элементов из самого списка.

Здравствуйте, cthutq00, Вы писали:

C>возникли сложности с подходящим алгоритмом

Именно алгоритм? Руками в for'е сделать что-то мешает?

Что касается слияния списков... напрашивается создание массива итераторов на разно-type-ные элементы.
Тогда алгоритмы будут линейными. В противном случае — квадратными.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, cthutq00, Вы писали:

C>>возникли сложности с подходящим алгоритмом

К>Именно алгоритм? Руками в for'е сделать что-то мешает?

К>Что касается слияния списков... напрашивается создание массива итераторов на разно-type-ные элементы.
К>Тогда алгоритмы будут линейными. В противном случае — квадратными.

причем в случае када нада поскладывать элементы одного списка это можно делать за один проход... -- делать индекс и складывать одновременно

насчет векторов и конструкторов: если конструктор|деструктор дорогая (реально дорогая а не просто инициализация числовых датамемберов) операция выдели все дорогое в отдельный storage а в S храни boost::shared_ptr -- подсчет ссылок те должен помочь. Если в S всего "пара интов" то забей

Здравствуйте, zaufi, Вы писали:

К>>Что касается слияния списков... напрашивается создание массива итераторов на разно-type-ные элементы.
К>>Тогда алгоритмы будут линейными. В противном случае — квадратными.

Z>причем в случае када нада поскладывать элементы одного списка это можно делать за один проход... -- делать индекс и складывать одновременно

Да и в случае двух списков... Сперва пробежались по первому, собрали индекс (заодно, если нужно, устранили дубликаты); затем побежали по второму, сверяясь с индексом первого.

Z>насчет векторов и конструкторов: если конструктор|деструктор дорогая (реально дорогая а не просто инициализация числовых датамемберов) операция выдели все дорогое в отдельный storage а в S храни boost::shared_ptr -- подсчет ссылок те должен помочь. Если в S всего "пара интов" то забей

... и/или реализуй механизм COW (copy on write).
На shared_ptr это легко и просто.

Здравствуйте, _DAle_, Вы писали:

_DA>Я так понял, что не каждый с каждым, а сложить соответствующие элементы векторов.

C>>

C>>    std::transform (v1.begin(), v1.end(),
C>>            v2.begin(), v1.begin(),
C>>            std::plus<S>());

C>>

_DA>Ну вместо transform лучше использовать merge, мне кажется, в данном случае.

я впринципе и сделал изначально с transform, но мне не очень понравилось

_DA>Предлагаю завести map<T, int>, проитерироваться по списку, сбрасывая все в map, а потом построить новый list по полученному map'у. Если же enum никогда изменяться не будет (но вообще, лучше не делать таких предположений обычно), можно вместо map'a воспользоваться vector<int>.

ну во-первых то пример сверху довольно простой (был приведен для наглядности). и не совсем понят по чему
индексироваться в списке
во-вторых что произойдет с объектом если его помещать в map а там уже есть такой (неужели вызовется оператор +=)


_DA>Тут на самом деле не совсем понятно, что надо сделать. Предлагаю тоже самое, сначала забрасываем в map первый список, потом выборочно (проверяем, если такой элемент в map'е) забрасываем в map второй вместе с удалением забрасываемых элементов из самого списка.

что-то не совсем понятно как это сделать
также возникает сложность при модификации списка (т.к. итераторы становятся не действительными)

Z>>причем в случае када нада поскладывать элементы одного списка это можно делать за один проход... -- делать индекс и складывать одновременно

не совсем понял

К>Да и в случае двух списков... Сперва пробежались по первому, собрали индекс (заодно, если нужно, устранили дубликаты); затем побежали по второму, сверяясь с индексом первого.

в том то и дело, что их нужно не просто удалить, а еще и проссумировать со схожими

а как это сделать за один проход, если после удаления итераторы будут битыми

Z>>насчет векторов и конструкторов: если конструктор|деструктор дорогая (реально дорогая а не просто инициализация числовых датамемберов) операция выдели все дорогое в отдельный storage а в S храни boost::shared_ptr -- подсчет ссылок те должен помочь. Если в S всего "пара интов" то забей

К>... и/или реализуй механизм COW (copy on write).
К>На shared_ptr это легко и просто.

а можно примерчик, если не сложно — просто я про такое не слыхал

Здравствуйте, cthutq00, Вы писали:

C>ну во-первых то пример сверху довольно простой (был приведен для наглядности). и не совсем понят по чему
C>индексироваться в списке
C>во-вторых что произойдет с объектом если его помещать в map а там уже есть такой (неужели вызовется оператор +=)

Я не имел ввиду делать insert, я имел ввиду map_[list_iterator->type] += list_iterator->count;

_DA>>Тут на самом деле не совсем понятно, что надо сделать. Предлагаю тоже самое, сначала забрасываем в map первый список, потом выборочно (проверяем, если такой элемент в map'е) забрасываем в map второй вместе с удалением забрасываемых элементов из самого списка.

C>что-то не совсем понятно как это сделать
C>также возникает сложность при модификации списка (т.к. итераторы становятся не действительными)

При удалении из списка инвалидируется лишь итераторы и ссылки на удаленные элементы.

iterator erase(iterator position);
iterator erase(iterator first, iterator last);
...
3 Effects: Invalidates only the iterators and references to the erased elements.